package com.smh;

import org.junit.jupiter.api.Test;

import java.lang.reflect.Array;
import java.util.HashMap;

/**
 * @author shiminghui
 * @date 2025/3/7 9:38
 * @description: TODO
 */
public class _037_HashTable {
    @Test
    public void test() {
        HashTable<Integer, Integer> integerIntegerHashTable = new HashTable<>();
        integerIntegerHashTable.put(1, 1, 1);
        integerIntegerHashTable.put(2, 2, 1);
        integerIntegerHashTable.put(3, 3, 1);
        integerIntegerHashTable.put(17, 4, 1);
        System.out.println(integerIntegerHashTable.remove(1, 1));
    }

    @Test
    public void test2() {
        HashTable<Integer, Integer> integerIntegerHashTable = new HashTable<>(4);
        integerIntegerHashTable.put(1, 1, 1);
        integerIntegerHashTable.put(2, 2, 1);
        integerIntegerHashTable.put(3, 3, 1);
        integerIntegerHashTable.put(4, 4, 1);
        integerIntegerHashTable.put(5, 5, 1);
        integerIntegerHashTable.put(6, 6, 1);
        integerIntegerHashTable.put(7, 7, 1);
        integerIntegerHashTable.put(8, 8, 1);
        integerIntegerHashTable.resize();
    }

    @Test
    public void test3() {
        Integer i = 10;
        System.out.println(i.hashCode());

    }

    private static class HashTable<K, V> {
        private static final int DEFAULT_CAPACITY = 16;
        private static final float LOAD_FACTOR = 0.75f;
        private HashNode<K, V>[] table;
        private int size; // 当前hash表中的元素个数

        @SuppressWarnings("unchecked")
        public HashTable(int size) {
            if (size < 0) {
                throw new IllegalArgumentException("size must be greater than 0");
            }
            table = (HashNode<K, V>[]) Array.newInstance(HashNode.class, size);
        }

        public HashTable() {
            this(DEFAULT_CAPACITY);
        }

        public V get(K key) {
            return get(key.hashCode(), key);
        }

        public void put(K key, V value) {
            put(key.hashCode(), key, value);
        }

        public V remove(K key) {
            return remove(key.hashCode(), key);
        }

        public void resize() {
            if (size >= table.length * LOAD_FACTOR) {
                // 扩容
                HashNode<K, V>[] newTable = (HashNode<K, V>[]) Array.newInstance(HashNode.class, table.length << 1);
                for (int i = 0; i < table.length; i++) {
                    HashNode<K, V> p = table[i];
                    HashNode<K, V> pre = null;
                    HashNode<K, V> lastNewP = null;
                    if (p != null) {
                        // 拆分链表
                        while (p != null) {
                            int index = p.hash & (newTable.length - 1);
                            if (index != i) {
                                // 将该节点从原链表中删除
                                if (pre == null) {
                                    table[i] = p.next;
                                } else {
                                    // 将该节点从原链表中删除
                                    pre.next = p.next;
                                }
                                p.next = null;

                                // 将该节点插入到新链表尾部
                                if (lastNewP == null) {
                                    newTable[index] = p;
                                    lastNewP = p;
                                } else {
                                    lastNewP.next = p;
                                }

                            }
                            pre = p;
                            p = p.next;
                        }
                    }
                }
                System.arraycopy(table, 0, newTable, 0, table.length);
                table = newTable;
            }
        }


        /**
         * 根据hash值和key获取value
         *
         * @param hash
         * @param key
         * @return
         */
        public V get(int hash, K key) {
            // 求模运算转换为与运算,前提是数组长度必须是2的幂次方
            int index = hash & (table.length - 1);
            HashNode<K, V> kvHashNode = table[index];
            while (kvHashNode != null) {
                if (kvHashNode.hash == hash && kvHashNode.key.equals(key)) {
                    return kvHashNode.value;
                }
                kvHashNode = kvHashNode.next;
            }
            return null;
        }

        /**
         * key存在，更新value,不存在则插入
         *
         * @param hash
         * @param key
         * @param value
         */
        public void put(int hash, K key, V value) {
            int index = hash & (table.length - 1);
            HashNode<K, V> kvHashNode = table[index];
            if (kvHashNode == null) {
                kvHashNode = new HashNode<>(hash, key, value);
                table[index] = kvHashNode;
            } else {
                while (kvHashNode.next != null) {
                    if (kvHashNode.hash == hash && kvHashNode.key.equals(key)) {
                        kvHashNode.value = value;
                        return;
                    }
                    kvHashNode = kvHashNode.next;
                }
                // 将新节点插入到链表尾部
                kvHashNode.next = new HashNode<>(hash, key, value);
            }
            size++;

        }

        /**
         * 根据hash值和key删除value
         *
         * @param hash
         * @param key
         * @return 删除的value
         */
        public V remove(int hash, K key) {
            int index = hash & (table.length - 1);
            HashNode<K, V> kvHashNode = table[index];
            HashNode<K, V> pre = null;
            while (kvHashNode != null) {
                if (kvHashNode.hash == hash && kvHashNode.key.equals(key)) {
                    if (pre == null) {
                        table[index] = kvHashNode.next;
                    } else {
                        pre.next = kvHashNode.next;
                    }
                    size--;
                    return kvHashNode.value;
                }
                pre = kvHashNode;
                kvHashNode = kvHashNode.next;
            }
            return null;
        }


        private static class HashNode<K, V> {
            int hash; // hash值
            private K key;
            private V value;
            private HashNode<K, V> next;

            public HashNode(int hash, K key, V value) {
                this.hash = hash;
                this.key = key;
                this.value = value;
            }

            public HashNode(int hash, K key, V value, HashNode<K, V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }

            public HashNode() {
            }

        }
    }


}
